Online Judge►LeetCode

[LeetCode] 5 - Longest Palindromic Substring

題意

求最長回文子字串。

解法

假設dp(i,j)代表從i到j的子字串是否為回文，得到下列遞迴式

1
2
dp(i,j) = 1 , if ( s[i] == s[j] && dp(i+1,j-1) == 1 ) 
	= 0 , else

心得

不得不說JavaScript真的是慢了許多 …

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if ( s.length <= 1 ) return s ;
    var nowMax = 1 , nowString = s[s.length-1] ;
    var dp = new Array(s.length+1);
    var copy = new Array(s.length+1);
    for (var i = 0; i < s.length+1 ; i++) {
        copy[i] = true ;
    }
    for (var i = 0 ; i < s.length+1; i++){
        dp[i] = copy.slice(0);
    }
    for ( var i = s.length - 1 ; i >= 0 ; i -- ){
        for ( var j = i + 1 ; j < s.length ; j ++ ){
            if ( s[i] === s[j] && dp[i+1][j-1] !== false ){
                dp[i][j] = true ;
                if ( j - i + 1 > nowMax ){
                    nowMax = j - i + 1 ;
                    nowString = s.substring(i,j+1) ;
                }
            } else {
                dp[i][j] = false ;
            }
        }
    }
    return nowString ;
};